package com.veal98.tree;

import com.veal98.bean.TreeNode;

public class ConstructBinaryTreeFromInorderAndPostorderTraversal_106 {

    public static void main(String[] args) {

    }

    public TreeNode buildTree(int[] inorder, int[] postorder) {
        // 左闭右开
        return buildTree1(inorder, 0, inorder.length,
                          postorder, 0, postorder.length);
    }

    /**
     * @param inorder (左闭右开)
     * @param inLeft inorder 数组的起始下标
     * @param inRight inorder 数组的终止下标
     * @param postorder (左闭右开)
     * @param postLeft postorder 数组的起始下标
     * @param postRight postorder 数组的终止下标
     * @return
     */
    private TreeNode buildTree1(int[] inorder, int inLeft, int inRight,
                                int[] postorder, int postLeft, int postRight) {
        // 没有元素了
        if (inRight - inLeft < 1) {
            return null;
        }
        // 只有一个元素了
        if (inRight - inLeft == 1) {
            return new TreeNode(inorder[inLeft]);
        }

        // 后序数组的最后一个节点为根节点
        TreeNode root = new TreeNode(postorder[postRight - 1]);
        // 在中序数组中找到根节点的位置
        int index = inLeft;
        for (; index < inRight; index ++) {
            if (inorder[index] == root.val) {
                break;
            }
        }

        // 构建左子树
        root.left = buildTree1(inorder, inLeft, index,
                               postorder, postLeft, postLeft + (index - inLeft));
        // 构建右子树
        root.right = buildTree1(inorder, index + 1, inRight,
                                postorder, postLeft + (index - inLeft), postRight - 1);

        return root;

    }

}
